home *** CD-ROM | disk | FTP | other *** search
/ MacHack 1997 / MacHack 1997.toast / Hacks / Hacks ’97 / Warrior’s Progress / source code / Source / Libraries / Trees / RedBlackNode.cp < prev    next >
Encoding:
Text File  |  1997-06-28  |  2.3 KB  |  143 lines  |  [TEXT/CWIE]
  1. // RedBlackNode.cp
  2.  
  3. #ifndef RedBlackNode_h
  4. #include "RedBlackNode.h"
  5. #endif
  6. #ifndef RedBlackTree_h
  7. #include "RedBlackTree.h"
  8. #endif
  9. #ifndef Swap_h
  10. #include "Swap.h"
  11. #endif
  12.  
  13. RedBlackNode::RedBlackNode()
  14.   : red( true )
  15.   {
  16.   }
  17.  
  18. RedBlackNode::~RedBlackNode()
  19.   {
  20.     if ( Owned() )
  21.         Owner().Remove( *this );
  22.   }
  23.  
  24. RedBlackTree& RedBlackNode::DownCast( Tree& n )
  25.   {
  26.     return static_cast< RedBlackTree& >( n );
  27.   }
  28.     
  29. const RedBlackTree& RedBlackNode::DownCast( const Tree& n )
  30.   {
  31.     return static_cast< const RedBlackTree& >( n );
  32.   }
  33.  
  34. uint32 RedBlackNode::RedChildren() const
  35.   {
  36.     return ( HasLeftChild() ? Left()->red : 0 )
  37.             +( HasRightChild() ? Right()->red : 0 );
  38.   }
  39.  
  40. void RedBlackNode::SwapWith( RedBlackNode& partner )
  41.   {
  42.     Swap( red, partner.red );
  43.     TreeNode::SwapWith( partner );
  44.   }
  45.  
  46. void RedBlackNode::RotateUp()
  47.   {
  48.     Assert( !IsRoot() );
  49.     
  50.     if ( IsBlack() )
  51.       {
  52.         if ( IsLeftChild() )
  53.           {
  54.             Assert( Parent()->HasRightChild() );
  55.             Assert( Parent()->Right()->IsBlack() );
  56.             Parent()->Right()->red = true;
  57.             
  58.             Assert( HasLeftChild() );
  59.             Assert( Left()->IsRed() );
  60.             Left()->red = false;
  61.           }
  62.          else
  63.           {
  64.             Assert( IsRightChild() );
  65.             
  66.             Assert( Parent()->HasLeftChild() );
  67.             Assert( Parent()->Left()->IsBlack() );
  68.             Parent()->Left()->red = true;
  69.             
  70.             Assert( HasRightChild() );
  71.             Assert( Right()->IsRed() );
  72.             Right()->red = false;
  73.           }
  74.       }
  75.  
  76.     Swap( red, Parent()->red );
  77.     
  78.     TreeNode::RotateUp();
  79.   }
  80.  
  81. void RedBlackNode::Raise()
  82.   {
  83.     Assert( IsBlack() );
  84.     Assert( RedChildren() == 2 );
  85.     
  86.     red = true;
  87.     Left()->red = false;
  88.     Right()->red = false;
  89.   }
  90.  
  91. void RedBlackNode::Lower()
  92.   {
  93.     Assert( IsRed() );
  94.     Assert( HasLeftChild() );
  95.     Assert( HasRightChild() );
  96.     Assert( Left()->IsBlack() );
  97.     Assert( Right()->IsBlack() );
  98.     
  99.     red = false;
  100.     Left()->red = true;
  101.     Right()->red = true;
  102.   }
  103.  
  104. bool RedBlackNode::Valid( uint32 blackHeight ) const
  105.   {
  106.     if ( !TreeNode::Valid() )
  107.         return false;
  108.  
  109.     if ( red && !IsRoot() && Parent()->red )
  110.         return false;
  111.     
  112.     if ( IsBlack() )
  113.       {
  114.         if ( blackHeight == 0 )
  115.             return false;
  116.         blackHeight--;
  117.       }
  118.     
  119.     if ( Left() == 0 )
  120.       {
  121.         if ( blackHeight > 0 )
  122.             return false;
  123.       }
  124.      else
  125.       {
  126.         if ( !Left()->Valid( blackHeight ) )
  127.             return false;
  128.       }
  129.     
  130.     if ( Right() == 0 )
  131.       {
  132.         if ( blackHeight > 0 )
  133.             return false;
  134.       }
  135.      else
  136.       {
  137.         if ( !Right()->Valid( blackHeight ) )
  138.             return false;
  139.       }
  140.     
  141.     return true;
  142.   }
  143.